package cn.cxq.learning.tree;

import java.util.ArrayList;

/**
 * 剑指offer
 * 二叉树中和为某一值的路径
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：705868
 * 本题知识点： 树
 *  算法知识视频讲解
 * 题目描述
 * 输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
 * 示例1
 * 输入
 * 复制
 * {10,5,12,4,7},22
 * 返回值
 * 复制
 * [[10,5,7],[10,12]]
 * 示例2
 * 输入
 * 复制
 * {10,5,12,4,7},15
 * 返回值
 * 复制
 * []
 */
public class FindPath {

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {

        ArrayList<ArrayList<Integer>> result = new ArrayList<>();

        if (root == null) {
            return result;
        }

        ArrayList<Integer> path = new ArrayList<>();

        findPath(root,path,result,target);

        return result;
    }

    private void findPath(TreeNode node, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> result,int target) {

        ArrayList<Integer> nextLevelPath = new ArrayList<>(path); // 保存这一层应有的路径形式

        nextLevelPath.add(node.val); // 加上这一层的值

        if (node.left == null && node.right == null) { // 如果这个节点没有子节点了，就是叶子节点，那就可以算一下整个路径下来的和，如果符合就将路径保存
            int sum = 0;
            for (Integer integer : nextLevelPath) {
                sum+=integer;
            }
            if (sum == target) {
                result.add(nextLevelPath);
            }
        }

        if (node.left != null) {
            findPath(node.left, nextLevelPath, result, target);
        }

        if (node.right != null) {
            findPath(node.right, nextLevelPath, result, target);
        }
    }
}
